#pragma once

enum State
{
	EXIST,
	EMPTY,
	DELETE
};

template<class K, class T>
struct HashData
{
	pair<K, T> _kv;
	State _state = EMPTY;
};

template<class K, class T>
class Hash
{
public:
	Hash(int n = 10)
	{
		_table.resize(n);
	}

	HashData<K, T>* find(const K& key)
	{
		int hashi = key % _table.size();
		while (_table[hashi]._state != EMPTY)
		{
			if (_table[hashi]._kv.first == key && _table[hashi]._state == EXIST)
			{
				return &_table[hashi];
			}
			++hashi;
			hashi %= _table.size();
		}
		return nullptr;
	}

	bool insert(const pair<K, T>& kv)
	{
		if (_n * 10 / _table.size() >= 7)
		{
			Hash<K, T> newhash(_table.size() * 2);
			for (int i = 0; i < _table.size(); ++i)
			{
				if (_table[i]._state == EXIST)
				{
					newhash.insert(_table[i]._kv);
				}
			}
			_table.swap(newhash._table);
		}

		int hashi = kv.first % _table.size();
		while (_table[hashi]._state == EXIST)
		{
			if (_table[hashi]._kv.first == kv.first)
			{
				return false;
			}
			++hashi;
			hashi %= _table.size();
		}
		_table[hashi]._kv = kv;
		_table[hashi]._state = EXIST;
		++_n;
		return true;
	}
	bool erase(const K& key)
	{
		/*int hashi = key % _table.size();
		while (_table[hashi]._state != EMPTY)
		{
			if (_table[hashi]._kv.first == key && _table[hashi]._state == EXIST)
			{
				_table[hashi]._state = DELETE;
				return true;
			}
			++hashi;
			hashi %= _table.size();
		}
		return false;*/

		HashData<K, T>* tmp = find(key);
		if (tmp)
		{
			tmp->_state = DELETE;
			return true;
		}
		return false;
	}
private:
	vector<HashData<K, T>> _table;
	int _n = 0;
};

namespace hash_bucket
{
	template<class K, class T>
	struct HashNode
	{
		pair<K, T> _kv;
		HashNode* _next;
		HashNode(const pair<K, T>& kv)
		{
			_kv = kv;
			_next = nullptr;
		}
	};

	template<class K, class T>
	class Hash
	{
		typedef HashNode<K, T> Node;
	public:
		Hash(int n = 10)
		{
			_table.resize(n, nullptr);
			_n = 0;
		}
		~Hash()
		{
			for (int i = 0; i < _table.size(); ++i)
			{
				Node* cur = _table[i];
				while (cur)
				{
					Node* next = cur->_next;
					delete cur;
					cur = next;
				}
			}
		}
		bool insert(const pair<K, T>& kv)
		{
			if (_n == _table.size())
			{
				vector<Node*> NewTable(2 * _n, nullptr);
				for (int i = 0; i < _n; ++i)
				{
					Node* cur = _table[i];
					//
					while (cur)
					{
						Node* next = cur->_next;
						int hashi = cur->_kv.first % (2 * _n);
						cur->_next = NewTable[hashi];
						NewTable[hashi] = cur;
						cur = next;
					}
					_table[i] = nullptr;
				}
				_table.swap(NewTable);
			}
			int hashi = kv.first % _table.size();
			Node* NewNode = new Node(kv);
			NewNode->_next = _table[hashi];
			_table[hashi] = NewNode;
			++_n;
			return true;
		}
		Node* find(const K& key)
		{
			int hashi = key % _table.size();
			Node* cur = _table[hashi];
			while (cur)
			{
				if (cur->_kv.first == key)
				{
					break;
				}
				cur = cur->_next;
			}
			return cur;
		}
		bool erase(const K& key)
		{
			int hashi = key % _table.size();
			Node* cur = _table[hashi];
			Node* prev = nullptr;
			while (cur)
			{
				if (cur->_kv.first == key)
				{
					if (prev)
					{
						prev->_next = cur->_next;
					}
					else
					{
						_table[hashi] = cur->_next;
					}
					delete cur;
					--_n;
					return true;
				}
				prev = cur;
				cur = cur->_next;
			}
			return false;
		}
	private:
		vector<Node*> _table;
		int _n;
	};
	void test01()
	{
		Hash<int, int> h(5);
		h.insert({ 3, 3 });
		h.insert({ 8, 8 });
		h.insert({ 2, 2 });
		h.insert({ 7, 7 });
		h.insert({ 1, 1 });
		h.insert({ 6, 6 });
		h.insert({ 11, 11 });
		h.erase(11);
	}
}